class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        col = [0] * n

        def dfs(r,s):
            if r == n:
                ans.append(['.' * c + 'Q' + '.'*(n-c-1) for c in col])
                return
            for c in s:
                if all(r+c != R+col[R] and r-c != R- col[R] for R in range(r)):
                    col[r] = c
                    dfs(r+1,s-{c})
                
        dfs(0,set(range(n)))
        return ans


# 大佬写法
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        col = [0] * n
        path = [False] * n
        m = n * 2
        dg = [False] * m
        udg = [False] * m


        def dfs(r):
            if r == n:
                ans.append(['.' * c + 'Q' + '.'*(n-c-1) for c in col])
                return

            for c in range(n):
                if not path[c] and not dg[r+c] and not udg[r-c]:
                    col[r] = c
                    path[c] = dg[r+c] = udg[r-c] = True
                    dfs(r+1)
                    path[c] = dg[r+c] = udg[r-c] = False
                
        dfs(0)
        return ans


